#leetcode题目35：搜索插入位置
#难度：简单
#时间复杂度：O(logn)
#空间复杂度：O(1)
#方法：二分查找

#暗示：时间复杂度为O(logn)，所以使用二分查找

from typing import List
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0    
        left,right=0,len(nums)-1#下标位
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return left




#测试数据
nums=[1,3,5,6]
target=5
#预期输出：2
solution=Solution()
print(solution.searchInsert(nums,target))

nums=[1,3,5,6]
target=2
#预期输出：1
solution=Solution()
print(solution.searchInsert(nums,target))

nums=[1,3,5,6]
target=7
#预期输出：4
solution=Solution()
print(solution.searchInsert(nums,target))